package Hard;

import java.util.ArrayDeque;
import java.util.Deque;

// 1425.带限制的子序列和
// dp[i]表示右端点为i的最大的子序列和
// dp[0] = nums[0]
// dp[i] = max(max(dp[i-Q])+nums[i],nums[i]) ; Q = 1,2,...,k
// 化简得 dp[i] = max(dp[i-Q],0) + nums[i]; Q = 1,2,...,k
// 返回dp里最大的值
// -----------------------------------------------------------
// 上面的方法会超时，看了答案的思路，需要使用单调队列（单调栈）进行维护，避免多余的运算
// 单调栈原理：
// 如果dp[i] > dp[i-1] 则每次挑选max的时候，就不要去和dp[i-1]比了，因此用栈来存放可以用来比的数
public class Solution1425 {
    public int constrainedSubsetSum(int[] nums, int k) {
        int length = nums.length;
        int[] dp = new int[length];
        dp[0] = nums[0];
        int ans = dp[0];
        // 使用单调队列（因为要从队首获取当前最大的子序列和，队尾插入新元素）
        Deque<Integer> deque = new ArrayDeque<Integer>();
        deque.addLast(0);
        for (int i = 1; i < dp.length; i++) {
            int max = 0;
            // 获取队首元素，队首元素是当前数前面为止的最大子序列和，但是如果他们的距离超过k，就先更新队列，再获取队首元素
            while(!deque.isEmpty() && i-deque.peekFirst() > k){
                deque.removeFirst();
            }
            // 获取队首元素
            int firstValue = dp[deque.peekFirst()];
            max = Math.max(0,firstValue);
            dp[i] = max+nums[i];
            ans = Math.max(ans,dp[i]);
            // 维护队列的单调性，如果新加入的这个dp值，比原来队首的要大，则清空队列，让队列里只剩下一个元素，就是dp[i]
            // 不能这么做，这么做无法保证队首是最大的子序列和所对应的下标
            // 正确做法：
            // 每次新加入一个元素以后，要保证当前队列里，没有比这个元素要大的子序列和
            while (!deque.isEmpty() && dp[i] > dp[deque.peekLast()]){
                deque.removeLast();
            }
            //最后，加入这个元素
            deque.addLast(i);
            /*
            if(dp[i] > firstValue){
                deque.clear();
                deque.addLast(i);
            }else {
                // 否则，将这个dp值加入
                deque.addLast(i);
            }
             */

        }
        return ans;
    }
}
